#include <vector>
class Solution {
    int m,n;
    bool vis[1005][1005];
public:
    int solve(vector<vector<int> >& matrix) {
        m=matrix.size(),n=matrix[0].size();
        int ans=0;
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                ans=max(ans,dfs(matrix,i,j));
            }
        }
        return ans;
    }

    int dx[4]={1,-1,0,0};
    int dy[4]={0,0,-1,1};

    int dfs(vector<vector<int> >& matrix,int x,int y)
    {
        vis[x][y]=true;
        int res=1;
        for(int k=0;k<4;k++)
        {
            int i=x+dx[k];
            int j=y+dy[k];
            if(i>=0&&i<m&&j>=0&&j<n&&!vis[i][j]&&matrix[i][j]>matrix[x][y])
            {
                res=max(res,dfs(matrix,i,j)+1);
            }
        }
        vis[x][y]=false;
        return res;
    }
};



//记忆化搜索优化
#include <vector>
class Solution {
    int m,n;
    int dx[4]={1,-1,0,0};
    int dy[4]={0,0,-1,1};
    int memo[1005][1005];
public:
    int solve(vector<vector<int> >& matrix) {
        m=matrix.size(),n=matrix[0].size();
        int ans=0;
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                ans=max(ans,dfs(matrix,i,j));
            }
        }
        return ans;
    }

    int dfs(vector<vector<int> >& matrix,int x,int y)
    {
        if(memo[x][y]!=0) return memo[x][y];
        int res=1;
        for(int k=0;k<4;k++)
        {
            int i=x+dx[k];
            int j=y+dy[k];
            if(i>=0&&i<m&&j>=0&&j<n&&matrix[i][j]>matrix[x][y])
            {
                res=max(res,dfs(matrix,i,j)+1);
            }
        }
        memo[x][y]=res;
        return res;
    }
};